package 剑指offer;

import leetcode.day_2020_12_14_12_21.TreeNode;

import java.util.*;

public class Offer07_JZ04 {

    public static TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        int preBegin = 0, preEnd = pre.length;
        int inBegin = 0, inEnd = in.length;
        return buildTree(preBegin, preEnd, pre, inBegin, inEnd, in);
    }

    public static TreeNode buildTree(int preBegin, int preEnd, int[] pre, int inBegin, int inEnd, int[] in) {
        // [1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
        if (preBegin == preEnd || inBegin == inEnd) return null;
        int rootVal = pre[preBegin];
        int len = calLen(rootVal, inBegin, in);
        TreeNode root = new TreeNode(rootVal);
        root.left = buildTree(preBegin+1, preBegin+len+1, pre, inBegin, inBegin+len+1, in);
        root.right = buildTree(preBegin+len+1, preEnd, pre, inBegin+len+1, inEnd, in);
        return root;
    }

    public static int calLen(int val, int begin, int[] in) {
        for (int i=begin; i<in.length; i++) {
            if (in[i] == val) {
                return i-begin;
            }
        }
        return 0;
    }
}
